import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1743 {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> record = new HashMap<>();
        for (int[] pair:adjacentPairs) {
            int left = pair[0];
            int right = pair[1];
            List<Integer> leftList = record.getOrDefault(left,new ArrayList<>());
            List<Integer> rightList = record.getOrDefault(right,new ArrayList<>());
            leftList.add(right);
            rightList.add(left);
            record.put(left,leftList);
            record.put(right, rightList);
        }

        int[] res = new int[adjacentPairs.length+1];
        for (Map.Entry et:record.entrySet()) {
            if(((List<Integer>)et.getValue()).size()==1){
                res[0] = (Integer) et.getKey();
            }
        }

        for (int i = 0; i < res.length-1; i++) {
            int tmp = res[i];
            int next = 0;
            if(i == 0){
                next = record.get(tmp).get(0);
            }
            else{
                int last = res[i-1];
                List<Integer> list = record.get(tmp);
                for (int num:list) {
                    if(num != last){
                        next = num;
                        break;
                    }
                }
            }
            res[i+1] = next;
        }

        return res;
    }

    public static void main(String[] args) {
        Solution1743 s = new Solution1743();
        System.out.println(s.restoreArray(new int[][]{{2,1},{3,4},{3,2}}));
    }
}
